/**
 * TreeBase.java created by zhangzhidong 
 * at 下午11:11:05 2016年4月19日
 */
package algorithm.CIG.base;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.function.Consumer;

/**
 * @author zhangzhidong
 *
 */
public class TreeBase {
	public static void morrisIn(TreeNode head){
		if(head==null) return;
		TreeNode cur = head;
		TreeNode cur2 = null;
		while(cur!=null){
			cur2 = cur.left;
			if(cur2!=null){
				while(cur2.right!=null && cur2.right!=cur){
					cur2 = cur2.right;
				}
				if(cur2.right==null){
					cur2.right = cur;
					cur = cur.left;
					continue;
				}else{
					cur2.right = null;
				}
			}
			System.out.println(cur + " ");
			cur = cur.right;
		}
		
		
		
		
		
	}
	
	
	
	
	
	public static void sepratorLine(){
		System.out.println("======================================================");
	}
	public static boolean isBalanceBinaryTree(TreeNode head){
		if(head==null) return true;
		boolean result[] = new boolean[1];
		result[0] = true;
		banlanceGetHeight(head, 1, result);
		return result[0];
	}
	private static int banlanceGetHeight(TreeNode node,int level,boolean result[]){
		if(node == null) return level;
		int lH =  banlanceGetHeight(node.left, level+1,result);
		if(!result[0]){
			return level;
		}
		int rH = banlanceGetHeight(node.right, level+1,result);
		if(!result[0]){
			return level;
		}
		if(Math.abs(lH-rH)>1){
			result[0] = false;
		}else{
			result[0] = true;
		}
		return Math.max(lH, rH);
	}
	
	
	public static TreeNode generateBSTWithWrong(){
		TreeNode head = new TreeNode(5);
		head.left = new TreeNode(3);
		head.right = new TreeNode(7);
		head.left.left = new TreeNode(2);
		head.left.right = new TreeNode(1);
		head.right.left = new TreeNode(6);
		head.right.right = new TreeNode(8);
		head.left.left.left = new TreeNode(4);
		return head;
	}
	public static TreeNode generateTree(){
		TreeNode head = new TreeNode(5);
		head.left = new TreeNode(3);
		head.right = new TreeNode(8);
		head.left.left = new TreeNode(2);
		head.left.right = new TreeNode(4);
		head.left.left.left = new TreeNode(1);
		head.right.left = new TreeNode(7);
		head.right.left.left = new TreeNode(6);
		head.right.right = new TreeNode(10);
		head.right.right.left = new TreeNode(9);
		head.right.right.right = new TreeNode(11);
		return head;
	}
	public static int getTreeHeight(TreeNode tn,int l){
		if(tn==null){
			return l;
		}else{
			return Math.max(getTreeHeight(tn.left,l+1),getTreeHeight(tn.right,l+1));
		}
	}
	
	public static void preTraverseNoRe(TreeNode head,Consumer<TreeNode> visitor){
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(head);
		while(!stack.isEmpty()){
			TreeNode tn = stack.pop();
			visitor.accept(tn);
			if(tn.right!=null){
				stack.push(tn.right);
			}
			if(tn.left!=null){
				stack.push(tn.left);
			}
		}
		
	}
	
	public static void postTraverseNoRe(TreeNode head,Consumer<TreeNode>visitor){
		
	}
	
	
	public static void inTraverseNoRe(TreeNode head,Consumer<TreeNode>visitor){
		Stack<TreeNode> stack = new Stack<TreeNode>();

		while(!stack.isEmpty()||head!=null){
			if(head!=null){
				stack.push(head);
				head = head.left;
			}else{
				head = stack.pop();
				visitor.accept(head);
				head = head.right;
			}
			
		}
		
	}
	
	public static void main(String args[]){
//		TreeNode t = generateTree();
//		System.out.println("tree height:"+getTreeHeight(t, 0));
//		inTraverseTree(t, System.out::println);
//		System.out.println("============");
//		inTraverseNoRe(t, System.out::println);
//		System.out.println("============");
		
		
		//判断平衡
		TreeNode t = generateBSTWithWrong();
		System.out.println(isBalanceBinaryTree(t));
		
	}
	public static void postTraverseTree(TreeNode root,Consumer<TreeNode>visitor){
		if(root==null){
			return ;
		}else{
			postTraverseTree(root.left, visitor);
			postTraverseTree(root.right, visitor);
			visitor.accept(root);
			
		}	
	}
	public static void inTraverseTree(TreeNode root,Consumer<TreeNode> visitor){
		if(root==null){
			return;
		}else{
			inTraverseTree(root.left, visitor);
			visitor.accept(root);
			inTraverseTree(root.right, visitor);
		}
	}
	
	public static void preTraverseTree(TreeNode root,Consumer<TreeNode> visitor){
		if(root == null){
			return ;
		}else{
			visitor.accept(root);
			preTraverseTree(root.left, visitor);
			preTraverseTree(root.right, visitor);
		}
	}
	
	public static String serialTreePre(TreeNode root){
		if(root==null){
			return "#!";
		}
		String res = root.val+"!";
		res += serialTreePre(root.left);
		res += serialTreePre(root.right);
		return res;
	}
	public static  TreeNode reConTree(String preStr){
		String []values = preStr.split("!");
		Queue<String> queue = new LinkedList<String>();
		for(int i=0;i<values.length;i++){
			queue.offer(values[i]);
		}
		return recon(queue);
	}
	private static TreeNode recon(Queue<String > queue){
		String value = queue.poll();
		if(value.equals("#")){
			return null;
		}
		TreeNode head = new TreeNode(Integer.parseInt(value));
		head.left = recon(queue);
		head.right = recon(queue);
		return head;
	}
}
